// BranchNBound.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "Bins.h"
#include "Strip.h"
#include <time.h>
#include <stdlib.h>

bool GetBestUpperboundUnfilledStrip(CStripList stripList, CBinList binList, float *globalIncumbentSolution);
float GetEstimatedLowerboundForUnfilledStrip(CStripList stripList, CBinList binList);
bool Traversing(CStripList stripList, CBinList binList, float *globalIncumbentSolution);
bool StillContinue();//0 if timeout, 1 if not
bool ReadData(const char* lpszFileName, int *nBin, int *nStrip, float **stripHeight);
bool WriteData(const char* lpszFileName, int stripSize, int binSize, float incumbentSolution, CBinList &binList);
int compare (const void * a, const void * b);
void PrintSolution(CStripList &stripList, CBinList &binList, float incumbentSolution);
bool ReadFileName(const char* lpszFileName, char* lpszFileNameInput, char* lpszFileNameOutput, int *time_limit);
bool IsSolutionOptimal(CBinList &binList);

int TIME_LIMIT = 5*60; //minutes

time_t  currentTime, startTime;
float total = 0;
char fileNameInput[20], fileNameOutput[20];
		
int main(int argc, char* argv[])
{
	int binSize, stripSize;
	float *stripHeight = NULL;
	if (stripHeight!=NULL)
		delete stripHeight;
	int time_limit = 5;

	if (!ReadFileName("FileName.txt", fileNameInput, fileNameOutput, &time_limit))
	{
		printf("Error reading input file!\r\n");
		return 0;
	}
	
	TIME_LIMIT = time_limit*60;

	//Read input
	if (!ReadData(fileNameInput, &binSize, &stripSize, &stripHeight))
	{
		printf("Error reading input file!\r\n");
		return 0;
	}

	//Sorting input
	qsort (stripHeight, stripSize, sizeof(float), compare);
	for (int i= 0; i<stripSize; i++)
		total += stripHeight[i];
	printf("\nTotal height: %0.2f\n",total);
	//Main variables
	CBinList binList(binSize);
	CStripList stripList(stripHeight, stripSize);
	//Get an incumbent solution
	float incumbentSolution = binSize*stripSize;
	time(&startTime);
	bool result = GetBestUpperboundUnfilledStrip(stripList, binList, &incumbentSolution);
	if (!result)
		return 0;
	//Traversing begins here
	Traversing(stripList, binList, &incumbentSolution);
	
	//Finish or timeout, write data
	//WriteData(fileNameOutput, stripSize, binSize, incumbentSolution);
	return 0;
}

bool Traversing(CStripList stripList, CBinList binList, float *globalIncumbentSolution)
{
	//If we reach the last node return to continue branching
	if (stripList.GetNumberOfUnfilledStrip()==0)
		return true;
	//If timeout return
	if (!StillContinue())
		return false;
	float incumbentSolution, estimatedLowerBound;
	//Estimate lower bound
	estimatedLowerBound = GetEstimatedLowerboundForUnfilledStrip(stripList, binList)+ binList.GetShortestAvailableBin()->CurrentHeight;
	//Bad node! return
	if (estimatedLowerBound > *globalIncumbentSolution)
		return true;
	int binSize = binList.GetSize();
	int currentUnfilledStrip = stripList.GetCurrentAvailableStrip();
	float currentUnfilledStripHeight = stripList.GetValue(currentUnfilledStrip).GetHeight();
	bool result = true;
	int binIndexToBranch;
	//Branching here
	//for (int i = binSize - 1; i>=0; i--)
	for (int i = 0; i<binSize; i++)
	{
		//Be careful,!!!!
		binIndexToBranch = binList.GetIndexAt(i);
		stripList.SetBinValue(currentUnfilledStrip, binIndexToBranch);
		binList.AddHeight(i, currentUnfilledStripHeight);
		result = GetBestUpperboundUnfilledStrip(stripList, binList, globalIncumbentSolution);
		if (!result)
			break;
		result = Traversing(stripList, binList, globalIncumbentSolution);
		binList.AddHeight(binList.FindPositionOfBinIndex(binIndexToBranch), -currentUnfilledStripHeight);
		//Reset the currently unfilled bin
		stripList.ResetBinValue(currentUnfilledStrip);
		if (!result)
			break;
	}
	return result;
}

bool GetBestUpperboundUnfilledStrip(CStripList stripList, CBinList binList, float *globalIncumbentSolution)
{
	//CBinList tempBinList(binList);
	bool result = true;
	int unfilledStripSize = stripList.GetNumberOfUnfilledStrip();
	float incumbentSolution;
	for (int i = 0; i < unfilledStripSize; i++)
	{
		binList.SetBinForUnfilledStrip(stripList, 0);
	}
	incumbentSolution = binList.GetLongestBinHeight();
	if (incumbentSolution < *globalIncumbentSolution)
	{
		PrintSolution(stripList, binList, incumbentSolution);
		*globalIncumbentSolution = incumbentSolution;
		WriteData(fileNameOutput, stripList.GetSize(), binList.GetSize(), incumbentSolution, binList);
		//Found the best solution
		if (IsSolutionOptimal(binList))
			result = false;
	}
	return result;
}

//The stripList should be sorted
float GetEstimatedLowerboundForUnfilledStrip(CStripList stripList, CBinList binList)
{
	if (stripList.GetLongestAvailableStrip() == NULL)
		return 0;
	float minimumFinishTime;
	int stripSize = stripList.GetNumberOfUnfilledStrip();
	int binSize = binList.GetSize();
	minimumFinishTime = stripList.GetLongestAvailableStrip()->GetHeight();
	if (stripSize<=binSize)
		return minimumFinishTime;
	int minimumNumberInABin = (stripSize + binSize - 1) / binSize;
	float finishTimeMinimum = 0;
	for (int j = 0 ; j< minimumNumberInABin; j++)
	{
		finishTimeMinimum += stripList.GetValueUnfilled(stripSize - j).GetHeight();
	}
		
	if (minimumFinishTime < finishTimeMinimum)
		minimumFinishTime = finishTimeMinimum;
	/*CStripList tempStripList(stripList, stripSize-minimumNumberInABin, false);
	float estimateFinishTimeForTheRest = GetEstimatedLowerboundForUnfilledStrip(tempStripList, binList);	
	if (minimumFinishTime < estimateFinishTimeForTheRest)
		minimumFinishTime = estimateFinishTimeForTheRest;*/
	return minimumFinishTime;
}

bool StillContinue()
{
	time(&currentTime);
	if (difftime(currentTime, startTime)> TIME_LIMIT)
		return false;
	return true;
}

bool ReadFileName(const char* lpszFileName, char* lpszFileNameInput, char* lpszFileNameOutput, int *time_limit)
{
	FILE* f = fopen(lpszFileName, "rt");
	
	if (f == NULL)
		return false;

	fscanf(f, "%d", time_limit);
	fscanf(f,"%s", lpszFileNameInput);
	fscanf(f,"%s", lpszFileNameOutput);
	fclose(f);

	return true;
}
bool ReadData(const char* lpszFileName, int *nBin, int *nStrip, float **stripHeight)
{
	FILE* f = fopen(lpszFileName, "rt");
	
	if (f == NULL)
		return false;

	fscanf(f,"%d", nBin);
	fscanf(f,"%d", nStrip);
	float w,h;
	*stripHeight = new float[*nStrip];
	for (int i = 0; i < *nStrip; i++)
	{
		fscanf(f,"%f", &w);
		fscanf(f,"%f", &h);
		(*stripHeight)[i] = h;
	}
	fclose(f);
	return true;
}

bool WriteData(const char* lpszFileName, int stripSize, int binSize, float incumbentSolution, CBinList &binList)
{
	FILE* f = fopen(lpszFileName, "a");
	
	if (f == NULL)
		return false;
	fprintf(f, "\nResult for %d objects %d strips is: %0.2f", stripSize, binSize, incumbentSolution);
	int i,j;
	for (i= 0; i<binSize; i++)
	{
		fprintf(f, "\nStrip %d height: %0.2f Content: \n", binList.mBinList[i].Index, binList.mBinList[i].CurrentHeight);
		for (j = 0; j< binList.mBinList[i].StackSize; j++)
			fprintf(f, " %0.2f", binList.mBinList[i].Stack[j]);
	}
	time(&currentTime);
	double elapsed = difftime(currentTime, startTime);
	fprintf(f,"\nAfter %d mins %d secs \n", ((int) elapsed )/ 60, ((int ) elapsed)%60);
	fprintf(f,"\n\n*****************\n");
	fclose(f);
	return true;
}

//Decreasing order
int compare (const void * a, const void * b)
{
	float result =  *(float*)a - *(float*)b;
	if (result < 0)
		return 1;
	else if (result > 0)
		return -1;
	else
		return 0;
}

void PrintSolution(CStripList &stripList, CBinList &binList, float incumbentSolution)
{
	int stripSize = stripList.GetSize();
	int i=0;
	for (i = 0; i< stripSize; i++)
		printf("%d\t",i);
	printf("\n");
	for (i = 0; i< stripSize; i++)
		printf("%0.2f\t",stripList.GetValue(i).GetHeight());
	printf("\n");
	for (i = 0; i< stripSize; i++)
		printf("%d\t",stripList.GetValue(i).GetBin());
	printf("\n");
	//Print the bin
	int binSize = binList.GetSize();
	for (i = 0; i< binSize; i++)
		printf("%d\t",binList.GetIndexAt(i));
	printf("\n");
	for (i = 0; i< binSize; i++)
		printf("%0.2f\t",binList.GetValueAt(i));
	printf("\nIncumbent Solution: %0.2f\n\n", incumbentSolution);
}

bool IsSolutionOptimal(CBinList &binList)
{
	float possibleDecreaseValue = (float) binList.GetLongestBinHeight() - 0.01;
	float valueIncrease = 0;
	int binSize = binList.GetSize();
	for (int i=0; i< binSize; i++)
		valueIncrease += possibleDecreaseValue - binList.GetValueAt(i);
	if (valueIncrease<0)
		return true;
	else
		return false;
}